{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Array Into Two Arrays to Minimize Sum Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #two-pointers #binary-search #dynamic-programming #bitmask #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #双指针 #二分查找 #动态规划 #状态压缩 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组分成两个数组并最小化数组和的差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>2 * n</code>&nbsp;的整数数组。你需要将&nbsp;<code>nums</code>&nbsp;分成&nbsp;<strong>两个</strong>&nbsp;长度为&nbsp;<code>n</code>&nbsp;的数组，分别求出两个数组的和，并 <strong>最小化</strong>&nbsp;两个数组和之&nbsp;<b>差的绝对值</b>&nbsp;。<code>nums</code>&nbsp;中每个元素都需要放入两个数组之一。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<strong>最小</strong>&nbsp;的数组和之差。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"example-1\" src=\"https://assets.leetcode.com/uploads/2021/10/02/ex1.png\" style=\"width: 240px; height: 106px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,9,7,3]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>最优分组方案是分成 [3,9] 和 [7,3] 。\n",
    "数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-36,36]\n",
    "<b>输出：</b>72\n",
    "<strong>解释：</strong>最优分组方案是分成 [-36] 和 [36] 。\n",
    "数组和之差的绝对值为 abs((-36) - (36)) = 72 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"example-3\" src=\"https://assets.leetcode.com/uploads/2021/10/02/ex3.png\" style=\"width: 316px; height: 106px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,-1,0,4,-2,-9]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。\n",
    "数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>nums.length == 2 * n</code></li>\n",
    "\t<li><code>-10<sup>7</sup> &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-array-into-two-arrays-to-minimize-sum-difference](https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-array-into-two-arrays-to-minimize-sum-difference](https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,7,3]', '[-36,36]', '[2,-1,0,4,-2,-9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        s1, s2 = sum(nums[:n]), sum(nums[n:])\n",
    "        ans = abs(s1 - s2)\n",
    "        \n",
    "        for i in range(1, (n >> 1) + 1):\n",
    "            f = sorted(2 * sum(x) - s1 for x in combinations(nums[:n], i))\n",
    "            for comb in combinations(nums[n:], n - i):\n",
    "                total = 2 * sum(comb) - s2\n",
    "                x = bisect.bisect_left(f, -total)\n",
    "                if x > 0:\n",
    "                    ans = min(ans, abs(f[x-1] + total))\n",
    "                if x < len(f):\n",
    "                    ans = min(ans, abs(f[x] + total))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "getres = lambda a, b, ts: min(abs(ts - ls * 2 - b[bisect_left(b, (ts - ls * 2) >> 1)] * 2) for ls in a)\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        return min(getres([sum(left) for left in combinations(nums[:n], l)], sorted([sum(right) for right in combinations(nums[n:], n - l)]) + [inf], sum(nums)) for l in range(n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        s1, s2 = sum(nums[:n]), sum(nums[n:])\n",
    "        ans = abs(s1 - s2)\n",
    "        \n",
    "        for i in range(1, (n >> 1) + 1):\n",
    "            f = sorted(2 * sum(x) - s1 for x in combinations(nums[:n], i))\n",
    "            for comb in combinations(nums[n:], n - i):\n",
    "                total = 2 * sum(comb) - s2\n",
    "                x = bisect.bisect_left(f, -total)\n",
    "                if x > 0:\n",
    "                    ans = min(ans, abs(f[x-1] + total))\n",
    "                if x < len(f):\n",
    "                    ans = min(ans, abs(f[x] + total))\n",
    "            if ans == 0 or ans == 1:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "getres = lambda a, b, ts: min(abs(ts - ls * 2 - b[bisect_left(b, (ts - ls * 2) >> 1)] * 2) for ls in a)\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        return min(getres([sum(left) for left in combinations(nums[:n], l)], sorted([sum(right) for right in combinations(nums[n:], n - l)]) + [inf], sum(nums)) for l in range(n + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        s1, s2 = sum(nums[:n]), sum(nums[n:])\n",
    "        ans = abs(s1 - s2)\n",
    "        \n",
    "        for i in range(1, (n >> 1) + 1):\n",
    "            f = sorted(2 * sum(x) - s1 for x in combinations(nums[:n], i))\n",
    "            for comb in combinations(nums[n:], n - i):\n",
    "                total = 2 * sum(comb) - s2\n",
    "                x = bisect.bisect_left(f, -total)\n",
    "                if x > 0:\n",
    "                    ans = min(ans, abs(f[x-1] + total))\n",
    "                if x < len(f):\n",
    "                    ans = min(ans, abs(f[x] + total))\n",
    "            if ans == 0 or ans == 1:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        res = inf; ts = sum(nums)\n",
    "        for l in range((n >> 1) + 1):\n",
    "            left_comb = sorted(sum(left) for left in combinations(nums[:n], l))\n",
    "            right_comb = sorted(sum(right) for right in combinations(nums[n:], n - l))\n",
    "            # print(left_comb, right_comb)\n",
    "            nn = len(left_comb)\n",
    "            pl, pr = 0, nn - 1\n",
    "            while pl < nn and pr >= 0:\n",
    "                part_sum = left_comb[pl] + right_comb[pr]\n",
    "                res = min(res, abs(ts - part_sum * 2))\n",
    "                if part_sum < ts / 2: pl += 1\n",
    "                else: pr -= 1\n",
    "            if res == 0: return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        ans=inf\n",
    "        n=len(nums)//2\n",
    "        summ=sum(nums)\n",
    "\n",
    "        dicc=defaultdict(list)\n",
    "\n",
    "        for i in range((1<<n)):\n",
    "            temp=0\n",
    "            t=0\n",
    "            for j in range(n):\n",
    "                \n",
    "                if (i>>j)&1:\n",
    "                    t+=1\n",
    "                    temp+=nums[j]\n",
    "\n",
    "            dicc[t].append(temp)\n",
    "\n",
    "\n",
    "        for i in dicc:\n",
    "            dicc[i].sort()\n",
    "\n",
    "        # print(dicc)\n",
    "\n",
    "        \n",
    "        for i in range((1<<n)):\n",
    "            temp=0\n",
    "            # l=dicc[n-i.bit_count()]\n",
    "            t=0\n",
    "            for j in range(n):\n",
    "                if (i>>j)&1:\n",
    "                    t+=1\n",
    "                    temp+=nums[n+j]\n",
    "            l=dicc[n-t]\n",
    "            index=bisect_left(l,summ/2-temp)\n",
    "            if index<len(l):\n",
    "                ans=min(ans,2*abs(summ/2-(temp+l[index])))\n",
    "            if index:\n",
    "                ans=min(ans,2*abs(summ/2-(temp+l[index-1])))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        ans=inf\n",
    "        n=len(nums)//2\n",
    "        summ=sum(nums)\n",
    "\n",
    "        dicc=defaultdict(list)\n",
    "\n",
    "        for i in range((1<<n)):\n",
    "            temp=0\n",
    "            for j in range(n):\n",
    "                \n",
    "                if (i>>j)&1:\n",
    "                    temp+=nums[j]\n",
    "\n",
    "            dicc[i.bit_count()].append(temp)\n",
    "\n",
    "\n",
    "        for i in dicc:\n",
    "            dicc[i].sort()\n",
    "\n",
    "        # print(dicc)\n",
    "\n",
    "        \n",
    "        for i in range((1<<n)):\n",
    "            temp=0\n",
    "            l=dicc[n-i.bit_count()]\n",
    "\n",
    "            for j in range(n):\n",
    "                if (i>>j)&1:\n",
    "                    temp+=nums[n+j]\n",
    "\n",
    "            index=bisect_left(l,summ/2-temp)\n",
    "            if index<len(l):\n",
    "                ans=min(ans,2*abs(summ/2-(temp+l[index])))\n",
    "            if index:\n",
    "                ans=min(ans,2*abs(summ/2-(temp+l[index-1])))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        ret = [[] for _ in range(n + 1)]\n",
    "        for i in range(1 << n):\n",
    "            cnt = s = 0\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    cnt += 1\n",
    "                    s += nums[j]\n",
    "                else:\n",
    "                    s -= nums[j]\n",
    "            ret[cnt].append(s)\n",
    "        for x in ret:\n",
    "            x.sort()\n",
    "        ans = abs(sum(nums[n:]) - ret[n][0])\n",
    "        for i in range(1 << n):\n",
    "            cnt = s = 0\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    cnt += 1\n",
    "                    s += nums[n + j]\n",
    "                else:\n",
    "                    s -= nums[n + j]\n",
    "            # print(nums, cnt, ret[cnt], s)\n",
    "            idx = bisect_left(ret[cnt], s)\n",
    "            if idx == len(ret[cnt]):\n",
    "                ans = min(ans, s - ret[cnt][-1])\n",
    "            else:\n",
    "                ans = min(ans, abs(s - ret[cnt][idx]))\n",
    "                if idx + 1 < len(ret[cnt]):\n",
    "                    ans = min(ans, ret[cnt][idx + 1] - s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        # 左边一半按着数量进行分类，计算出来所有的结果\n",
    "        # 然后枚举右边的结果, 如果右边只有一个数字，那么左边就是n//2-1个数字里面选\n",
    "        # 选的结果是什么呢？对应的arr，tot = l + r + res\n",
    "        # abs(l + r - res) = abs(l + r - tot + l + r) = abs(2l + 2r - tot)\n",
    "        # 采用状态空间进行优化\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        f = defaultdict(list)\n",
    "        for i in range(1 << m):\n",
    "            tot, t = 0, 0\n",
    "            k = i\n",
    "            while k:\n",
    "                lb = k & -k\n",
    "                k -= lb\n",
    "                tot += nums[lb.bit_length()-1]\n",
    "                t += 1\n",
    "            f[t].append(tot)\n",
    "        for k in f.keys():\n",
    "            f[k].sort()\n",
    "        ans = inf\n",
    "        for i in range(1 << m):\n",
    "            tot, t = 0, 0\n",
    "            k = i\n",
    "            while k:\n",
    "                lb = k & -k\n",
    "                k -= lb\n",
    "                tot += nums[lb.bit_length()-1 + m]\n",
    "                t += 1\n",
    "            arr = f[m-t]\n",
    "            idx = bisect_left(arr, (s - 2 * tot) // 2)\n",
    "            if idx > 0: ans = min(ans, abs(2 * arr[idx-1] + 2 * tot - s))\n",
    "            if idx < len(arr): ans = min(ans, abs(2 * arr[idx] + 2 * tot - s))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums):\n",
    "        n = len(nums) // 2\n",
    "        a, b = nums[:n], nums[n:]\n",
    "        total = sum(nums)\n",
    "        half_total = total / 2\n",
    "\n",
    "        # List indexed with length summation for b\n",
    "        # 创建不同组的列表，分别记录每个组中元素和的可能值\n",
    "        b_cnt_sum_map = [[] for _ in range(n + 1)]\n",
    "        for i in range(1 << n): # 2^n = 1 << n, # of combinations\n",
    "            sum_val, cnt = 0, 0\n",
    "            # j represents each indexed element of a, converts combination to element selection\n",
    "            for j, v in enumerate(b):   \n",
    "                if i >> j & 1:  # check if indexed element is selected\n",
    "                    sum_val += v\n",
    "                    cnt += 1\n",
    "\n",
    "            b_cnt_sum_map[cnt].append(sum_val)\n",
    "\n",
    "        # 对每个组的元素和进行排序\n",
    "        for tmp in b_cnt_sum_map:\n",
    "            tmp.sort()\n",
    "\n",
    "        res = sys.maxsize\n",
    "        # calculate sum combination for a, find match using bisect in b_cnt_sum_map\n",
    "        # select i elements from a with sum x, j elements from b with sum y, a + b = n\n",
    "        # goal is to minimize abs(sum - 2 * (x + y)) close to 0\n",
    "        # y = sum / 2 - x\n",
    "        for i in range(1 << n):\n",
    "            sum_val, cnt = 0, 0\n",
    "            for j, v in enumerate(a):\n",
    "                if i >> j & 1:\n",
    "                    sum_val += v\n",
    "                    cnt += 1\n",
    "\n",
    "            # 在对应的组里二分查找最接近的数\n",
    "            b_sum = b_cnt_sum_map[n - cnt]\n",
    "            j = bisect_left(b_sum, half_total - sum_val)\n",
    "            if j < len(b_sum):\n",
    "                res = min(res, abs(total - 2 * (sum_val + b_sum[j])))\n",
    "            if j > 0:\n",
    "                res = min(res, abs(total - 2 * (sum_val + b_sum[j - 1])))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums):\n",
    "        n = len(nums) // 2\n",
    "        a = nums[:n]\n",
    "\n",
    "        # 创建不同组的列表，分别记录每个组中元素和的可能值\n",
    "        res = [[] for _ in range(n + 1)]\n",
    "        for i in range(1 << n):\n",
    "            sum_val, cnt = 0, 0\n",
    "            for j, v in enumerate(a):\n",
    "                if i >> j & 1:\n",
    "                    sum_val += v\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    sum_val -= v\n",
    "            res[cnt].append(sum_val)\n",
    "\n",
    "        # 对每个组的元素和进行排序\n",
    "        for b in res:\n",
    "            b.sort()\n",
    "\n",
    "        ans = sys.maxsize\n",
    "        a = nums[n:]\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            sum_val, cnt = 0, 0\n",
    "            for j, v in enumerate(a):\n",
    "                if i >> j & 1:\n",
    "                    sum_val += v\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    sum_val -= v\n",
    "\n",
    "            # 在对应的组里二分查找最接近的数\n",
    "            b = res[cnt]\n",
    "            j = bisect_left(b, sum_val)\n",
    "            if j < len(b):\n",
    "                ans = min(ans, abs(b[j] - sum_val))\n",
    "            if j > 0:\n",
    "                ans = min(ans, abs(sum_val - b[j - 1]))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "def helper(lst, k):\n",
    "    return sorted(set(sum(x) for x in combinations(lst, k)))\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        s = sum(nums)\n",
    "        target = s / 2\n",
    "        left = nums[:n]\n",
    "        right = nums[n:]\n",
    "        min_diff = float('inf')\n",
    "        min_sum = 0\n",
    "        for k in range(n):\n",
    "            left_list = helper(left, k)\n",
    "            right_list = helper(right, n - k)\n",
    "            left_index = 0\n",
    "            right_index = len(right_list) - 1\n",
    "            while left_index < len(left_list) and right_index > -1:\n",
    "                cur_sum = left_list[left_index] + right_list[right_index]\n",
    "                cur_diff = abs(cur_sum - target)\n",
    "                if cur_diff < min_diff:\n",
    "                    min_diff = cur_diff\n",
    "                    min_sum = cur_sum\n",
    "                if cur_sum < target:\n",
    "                    left_index += 1\n",
    "                else:\n",
    "                    right_index -= 1\n",
    "        return abs(2 * min_sum - s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n_2 = len(nums)\n",
    "        n = n_2 // 2\n",
    "\n",
    "        pre, suf = nums[:n], nums[n:]\n",
    "        seen = defaultdict(SortedList)\n",
    "        for l in range(1, n):\n",
    "            for c in combinations(pre, l):\n",
    "                seen[l].add(sum(c))\n",
    "        \n",
    "        ans = abs(sum(pre) - sum(suf))\n",
    "        total = sum(nums)\n",
    "        half = total // 2\n",
    "        for l in range(1, n):\n",
    "            for c in combinations(suf, l):\n",
    "                t = sum(c)\n",
    "                idx = seen[n - l].bisect_left(half - t)\n",
    "                for i in (idx - 1, idx):\n",
    "                    if 0 <= i < len(seen[n - l]):\n",
    "                        ans = min(ans, abs(total - 2 * (t + seen[n - l][i])))\n",
    "                        if not ans:\n",
    "                            return 0\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n_2 = len(nums)\n",
    "        n = n_2 // 2\n",
    "\n",
    "        pre, suf = nums[:n], nums[n:]\n",
    "        seen = defaultdict(SortedList)\n",
    "        for l in range(1, n):\n",
    "            for c in combinations(pre, l):\n",
    "                seen[l].add(sum(c))\n",
    "        \n",
    "        ans = abs(sum(pre) - sum(suf))\n",
    "        total = sum(nums)\n",
    "        half = total // 2\n",
    "        for l in range(1, n):\n",
    "            for c in combinations(suf, l):\n",
    "                t = sum(c)\n",
    "                idx = seen[n - l].bisect_left(half - t)\n",
    "                for i in (idx - 1, idx):\n",
    "                    if 0 <= i < len(seen[n - l]):\n",
    "                        v = t + seen[n - l][i]\n",
    "                        ans = min(ans, abs(total - 2 * v))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "       n = len(nums) // 2\n",
    "       dic = collections.defaultdict(list)\n",
    "       for i in range(1 << n):\n",
    "          cnt = 0\n",
    "          _sum = 0\n",
    "          for j in range(n):\n",
    "             if ((i >> j) & 1) == 0:\n",
    "                cnt += 1\n",
    "                _sum += nums[j]\n",
    "             else:\n",
    "                _sum -= nums[j]\n",
    "          dic[cnt].append(_sum)\n",
    "       for c in dic.values():\n",
    "          c.sort()\n",
    "       res = inf\n",
    "       for i in range(1 << n):\n",
    "          cnt = 0\n",
    "          _sum = 0\n",
    "          for j in range(n):\n",
    "             if ((i >> j) & 1) == 0:\n",
    "                cnt += 1\n",
    "                _sum += nums[n + j]\n",
    "             else:\n",
    "                _sum -= nums[n + j]\n",
    "          _list = dic[n - cnt]\n",
    "          left = bisect.bisect_left(_list, -_sum)\n",
    "          if left != len(_list):\n",
    "             res = min(res, abs(_list[left] + _sum))\n",
    "          right = bisect.bisect_right(_list, -_sum)\n",
    "          if right != len(_list):\n",
    "             res = min(res, abs(_list[right] + _sum))\n",
    "          if res == 0:\n",
    "             break\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "       n = len(nums) // 2\n",
    "       dic = collections.defaultdict(list)\n",
    "      #  arr = [0] * n\n",
    "      #  for i in range(n):\n",
    "      #     arr[i] = nums[i]\n",
    "       for i in range(1 << n):\n",
    "          cnt = 0\n",
    "          _sum = 0\n",
    "          for j in range(n):\n",
    "             if ((i >> j) & 1) == 0:\n",
    "                cnt += 1\n",
    "                _sum += nums[j]\n",
    "             else:\n",
    "                _sum -= nums[j]\n",
    "          dic[cnt].append(_sum)\n",
    "       for c in dic.values():\n",
    "          c.sort()\n",
    "       res = inf\n",
    "      #  for i in range(n, n * 2):\n",
    "      #     arr[i - n] = nums[i]\n",
    "       for i in range(1 << n):\n",
    "          cnt = 0\n",
    "          _sum = 0\n",
    "          for j in range(n):\n",
    "             if ((i >> j) & 1) == 0:\n",
    "                cnt += 1\n",
    "                _sum += nums[n + j]\n",
    "             else:\n",
    "                _sum -= nums[n + j]\n",
    "          left = bisect.bisect_left(dic[n - cnt], -_sum)\n",
    "          if left != len(dic[n - cnt]):\n",
    "             res = min(res, abs(dic[n - cnt][left] + _sum))\n",
    "          right = bisect.bisect_right(dic[n - cnt], -_sum)\n",
    "          if right != len(dic[n - cnt]):\n",
    "             res = min(res, abs(dic[n - cnt][right] + _sum))\n",
    "          if res == 0:\n",
    "             break\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        leftLen = n // 2 \n",
    "        rightLen = n - n // 2 \n",
    "        left = collections.defaultdict(list)\n",
    "        for i in range(1, 1 << leftLen):\n",
    "            cnt = 0\n",
    "            s = 0\n",
    "            for j in range(leftLen):\n",
    "                if i & 1 << j:\n",
    "                    cnt += 1 \n",
    "                    s += nums[j]\n",
    "                else:\n",
    "                    s -= nums[j]\n",
    "            left[cnt].append(s)\n",
    "        for c in left:\n",
    "            left[c].sort()\n",
    "        res = float('inf')\n",
    "        for i in range(1, 1 << rightLen):\n",
    "            cnt = 0\n",
    "            s = 0\n",
    "            for j in range(leftLen, n):\n",
    "                if i & (1 << (j - leftLen)):\n",
    "                    cnt += 1 \n",
    "                    s += nums[j]\n",
    "                else:\n",
    "                    s -= nums[j]\n",
    "            idx = bisect_left(left[cnt], s)\n",
    "            if idx > 0:\n",
    "                res = min(res, s - left[cnt][idx - 1])\n",
    "            if idx < len(left[cnt]):\n",
    "                res = min(res, left[cnt][idx] - s)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums) // 2\n",
    "        left = [ [] for _ in range(n+1)]\n",
    "        right = [ [] for _ in range(n+1)]\n",
    "        \n",
    "        def dfs(nums,res,i,c,record):\n",
    "            if i == n:\n",
    "                record[c].append(res)\n",
    "                return \n",
    "            dfs(nums,res+nums[i],i+1,c+1,record)\n",
    "            dfs(nums,res-nums[i],i+1,c,record) \n",
    "        \n",
    "        dfs(nums[:n],0,0,0,left)\n",
    "        dfs(nums[n:],0,0,0,right)\n",
    "            \n",
    "        ret = inf\n",
    "        for i in range(n+1):\n",
    "            lvs = left[i]\n",
    "            rvs = right[i]\n",
    "            lvs.sort()\n",
    "            rvs.sort()\n",
    "            lvs.append(inf)\n",
    "            rvs.append(inf)\n",
    "            k,j = 0,0 \n",
    "            while k < len(lvs) and j < len(rvs) :\n",
    "                t  = lvs[k] - rvs[j]\n",
    "                if abs(t) < ret:      \n",
    "                   ret = abs(t)\n",
    "                if t == 0:\n",
    "                    return 0\n",
    "                if t < 0:\n",
    "                    k += 1 \n",
    "                else:\n",
    "                    j += 1\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "\n",
    "        def helper(shift=0):\n",
    "            pos = [[] for _ in range(n + 1)]\n",
    "            for mask in range(1 << n):\n",
    "                cur = 0\n",
    "                cnt = 0\n",
    "                for i in range(n):\n",
    "                    if mask >> i & 1:\n",
    "                        cnt += 1\n",
    "                        cur += nums[i + shift]\n",
    "                    else:\n",
    "                        cur -= nums[i + shift]\n",
    "                pos[cnt].append(cur)\n",
    "\n",
    "            for i in range(1, n):\n",
    "                pos[i].sort()\n",
    "            return pos\n",
    "\n",
    "        fi = helper()\n",
    "        se = helper(n)\n",
    "        # print(fi, \"\\n\", se)\n",
    "\n",
    "        res = min(abs(fi[0][0] + se[-1][0]), abs(fi[-1][0] + se[0][0]))\n",
    "        for i in range(1, n):\n",
    "            v = se[n - i]\n",
    "            for x in fi[i]:\n",
    "                j = bisect_left(v, -x)\n",
    "                if j < len(v):\n",
    "                    res = min(res, abs(x + v[j]))\n",
    "                if j > 0:\n",
    "                    res = min(res, abs(x + v[j - 1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        m = len(nums)\n",
    "        n = m // 2\n",
    "        tot = sum(nums)\n",
    "\n",
    "        def get_all(arr):\n",
    "            s = defaultdict(list)\n",
    "            for mask in range(1 << n):\n",
    "                cur = 0\n",
    "                for j in range(n):\n",
    "                    if mask & 1 << j:\n",
    "                        cur += arr[j]\n",
    "                s[mask.bit_count()].append(cur) \n",
    "            return s\n",
    "\n",
    "        left = get_all(nums[:n])\n",
    "        right = get_all(nums[n:])\n",
    "\n",
    "        for k, v in right.items():\n",
    "            v.sort()\n",
    "        # print(left, right, tot)\n",
    "        ans = inf\n",
    "        half = tot // 2\n",
    "        for le, v in left.items():\n",
    "            need = n - le\n",
    "            cand = right[need]\n",
    "            # if need == 1:\n",
    "            #     print(cand)\n",
    "            for num in v:\n",
    "                idx = bisect.bisect_right(cand, half - num)\n",
    "                # if need == 1:\n",
    "                #     print(num, idx, half - )\n",
    "                if idx < len(cand):\n",
    "                    ans = min(ans, abs(tot - num - cand[idx] - num - cand[idx]))\n",
    "                if idx > 0:\n",
    "                    ans = min(ans, abs(tot - num - cand[idx - 1] - num - cand[idx - 1]))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, a: List[int]) -> int:\n",
    "        s = sum(a)\n",
    "        n = len(a)//2\n",
    "        b = a[:n]\n",
    "        c = a[n:]\n",
    "        def f(x):\n",
    "            ans = [[0]]\n",
    "            while x:\n",
    "                t = x.pop()\n",
    "                ans.append([j+t for j in ans[-1]])\n",
    "                for j in range(1, len(ans)-1)[::-1]:\n",
    "                    ans[j]+=[k+t for k in ans[j-1]] \n",
    "            return ans \n",
    "        b = f(b)\n",
    "        c = f(c)\n",
    "        ans = float('inf')\n",
    "        for j in c:\n",
    "            j.sort()\n",
    "        for j in range(len(b)):\n",
    "            i = n-j\n",
    "            for k in b[j]:\n",
    "                ix = bisect_left(c[i], s/2 - k)\n",
    "                left = max(0, ix -1)\n",
    "                right = min(ix, len(c[i]) -1)\n",
    "                l = c[i][left]\n",
    "                r = c[i][right]\n",
    "                ans = min([ans, abs(k*2 + l*2 - s), abs(k*2 + r*2 - s)]) \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) >> 1\n",
    "        s = sum(nums)\n",
    "        fi = [[] for _ in range(n + 1)]\n",
    "        se = [[] for _ in range(n + 1)]\n",
    "        for mask in range(1 << n):\n",
    "            l = r = 0\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += 1\n",
    "                    l += nums[i]\n",
    "                    r += nums[i + n]\n",
    "\n",
    "            fi[cnt].append(l)\n",
    "            se[cnt].append(r)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            se[i].sort()\n",
    "\n",
    "        res = min(abs(s - 2 * fi[n][0]), abs(s - 2 * se[n][0]))\n",
    "\n",
    "        for i in range(1, n):\n",
    "            v = se[n - i]\n",
    "            for x in fi[i]:\n",
    "                y = (s - 2 * x) // 2\n",
    "                j = bisect_left(v, y)\n",
    "                if j < len(v):\n",
    "                    res = min(res, abs(s - 2 * (x + v[j])))\n",
    "                if j > 0:\n",
    "                    res = min(res, abs(s - 2 * (x + v[j - 1])))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums) // 2\n",
    "        left = [ [] for _ in range(n+1)]\n",
    "        right = [ [] for _ in range(n+1)]\n",
    "        \n",
    "        def dfs(nums,res,i,c,record):\n",
    "            if i == n:\n",
    "                #bisect.insort(record[c],res)  这个太慢了，后排序更快一点\n",
    "                record[c].append(res)\n",
    "                return \n",
    "            dfs(nums,res+nums[i],i+1,c+1,record)\n",
    "            dfs(nums,res-nums[i],i+1,c,record) \n",
    "        \n",
    "        dfs(nums[:n],0,0,0,left)\n",
    "        dfs(nums[n:],0,0,0,right)\n",
    "            \n",
    "        ret = inf\n",
    "        for i in range(n+1):\n",
    "            lvs = left[i]\n",
    "            rvs = right[i]\n",
    "            lvs.sort()\n",
    "            rvs.sort()\n",
    "            for lv in lvs:\n",
    "                k = bisect.bisect_left(rvs,lv)\n",
    "                if k < len(rvs):\n",
    "                    ret = min(ret,abs(rvs[k]-lv))\n",
    "                ret = min(ret,abs(rvs[k-1]-lv))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        s = sum(nums)\n",
    "        D1 = [[] for _ in range(n + 1)]\n",
    "        D2 = [[] for _ in range(n + 1)]\n",
    "        res = float('inf')\n",
    "        for msk in range(1 << n):\n",
    "            c, r1, r2 = 0, 0, 0\n",
    "            for i in range(n):\n",
    "                if msk & (1 << i):\n",
    "                    c += 1\n",
    "                    r1 += nums[i]\n",
    "                    r2 += nums[i + n]\n",
    "            D1[c].append(r1)\n",
    "            D2[c].append(r2)\n",
    "        for i in range(n + 1):\n",
    "            D1[i].sort()\n",
    "            D2[n - i].sort()\n",
    "            j1, j2 = 0, len(D2[n - i]) - 1\n",
    "            while j1 < len(D1[i]):\n",
    "                while j2 >= 0:\n",
    "                    k = D1[i][j1] + D2[n - i][j2]\n",
    "                    res = min(res, abs(2 * k - s))\n",
    "                    if 2 * k <= s:\n",
    "                        break\n",
    "                    j2 -= 1\n",
    "                j1 += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        s = sum(nums)\n",
    "        L = nums[:n]\n",
    "        pre_cnt = defaultdict(list)\n",
    "\n",
    "        def cal(x, Li):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    res += Li[i]\n",
    "            return res \n",
    "\n",
    "        def f(x):\n",
    "            return abs(s - 2 * x)\n",
    "\n",
    "        ans = inf \n",
    "        for i in range(1 << n):\n",
    "            pre_cnt[i.bit_count()].append(cal(i, L))\n",
    "        for k, v in pre_cnt.items():\n",
    "            pre_cnt[k] = [-inf] + sorted(set(v)) + [inf]\n",
    "        aft = nums[n:]\n",
    "        for i in range(1 << n):\n",
    "            tmp = cal(i, aft)\n",
    "            search = pre_cnt[n - i.bit_count()]            \n",
    "            ln = len(search)\n",
    "            if not ln:\n",
    "                continue \n",
    "            idx = bisect_left(search, s / 2 - tmp)\n",
    "            # if idx == ln:\n",
    "            #     ans = min(ans, f(tmp + search[-1]))\n",
    "            # elif search[idx] == s / 2 - tmp:\n",
    "            #     return 0\n",
    "            # elif idx == 0:\n",
    "            #     ans = min(ans, f(tmp + search[0]))\n",
    "            # else:\n",
    "            ans = min(ans, f(tmp + search[idx - 1]), f(tmp + search[idx]))\n",
    "            if ans == s % 2:\n",
    "                return s % 2\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums) // 2\n",
    "        left = [ [] for _ in range(n+1)]\n",
    "        right = [ [] for _ in range(n+1)]\n",
    "        \n",
    "        def dfs(nums,res,i,c,record):\n",
    "            if i == n:\n",
    "                #bisect.insort(record[c],res)  这个太慢了，后排序更快一点\n",
    "                record[c].append(res)\n",
    "                return \n",
    "            dfs(nums,res+nums[i],i+1,c+1,record)\n",
    "            dfs(nums,res-nums[i],i+1,c,record) \n",
    "        \n",
    "        dfs(nums[:n],0,0,0,left)\n",
    "        dfs(nums[n:],0,0,0,right)\n",
    "            \n",
    "        ret = inf\n",
    "        for i in range(n+1):\n",
    "            lvs = left[i]\n",
    "            rvs = right[i]\n",
    "            lvs.sort()\n",
    "            rvs.sort()\n",
    "            lvs.append(inf)\n",
    "            rvs.append(inf)\n",
    "            k,j = 0,0 \n",
    "            while k < len(lvs) and j < len(rvs) :\n",
    "                t  = lvs[k] - rvs[j]\n",
    "                if abs(t) < ret:      \n",
    "                   ret = abs(t)\n",
    "                if t == 0:\n",
    "                    return 0\n",
    "                if t < 0:\n",
    "                    k += 1 \n",
    "                else:\n",
    "                    j += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        s = sum(nums)\n",
    "        L = nums[:n]\n",
    "        pre_cnt = defaultdict(list)\n",
    "\n",
    "        def cal(x, Li):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    res += Li[i]\n",
    "            return res \n",
    "\n",
    "        def f(x):\n",
    "            return abs(s - 2 * x)\n",
    "\n",
    "        ans = inf \n",
    "        for i in range(1 << n):\n",
    "            pre_cnt[i.bit_count()].append(cal(i, L))\n",
    "        for k, v in pre_cnt.items():\n",
    "            pre_cnt[k] = sorted(set(v))\n",
    "        aft = nums[n:]\n",
    "        for i in range(1 << n):\n",
    "            tmp = cal(i, aft)\n",
    "            search = pre_cnt[n - i.bit_count()]            \n",
    "            ln = len(search)\n",
    "            if not ln:\n",
    "                continue \n",
    "            idx = bisect_left(search, s / 2 - tmp)\n",
    "            if idx == ln:\n",
    "                ans = min(ans, f(tmp + search[-1]))\n",
    "            elif search[idx] == s / 2 - tmp:\n",
    "                return 0\n",
    "            elif idx == 0:\n",
    "                ans = min(ans, f(tmp + search[0]))\n",
    "            else:\n",
    "                ans = min(ans, f(tmp + search[idx - 1]), f(tmp + search[idx]))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        s = sum(nums)\n",
    "        D1 = [[] for _ in range(n + 1)]\n",
    "        D2 = [[] for _ in range(n + 1)]\n",
    "        res = float('inf')\n",
    "        for msk in range(1 << n):\n",
    "            c, r1, r2 = 0, 0, 0\n",
    "            for i in range(n):\n",
    "                if msk & (1 << i):\n",
    "                    c += 1\n",
    "                    r1 += nums[i]\n",
    "                    r2 += nums[i + n]\n",
    "            D1[c].append(r1)\n",
    "            D2[c].append(r2)\n",
    "        for i in range(n + 1):\n",
    "            D1[i].sort()\n",
    "            D2[n - i].sort()\n",
    "            j1, j2 = 0, len(D2[n - i]) - 1\n",
    "            while j1 < len(D1[i]):\n",
    "                while j2 >= 0:\n",
    "                    k = D1[i][j1] + D2[n - i][j2]\n",
    "                    res = min(res, abs(2 * k - s))\n",
    "                    if 2 * k <= s:\n",
    "                        break\n",
    "                    j2 -= 1\n",
    "                j1 += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        m = len(nums)\n",
    "        n = m // 2\n",
    "        tot = sum(nums)\n",
    "\n",
    "        def get_all(arr):\n",
    "            s = defaultdict(list)\n",
    "            for mask in range(1 << n):\n",
    "                cur = 0\n",
    "                for j in range(n):\n",
    "                    if mask & 1 << j:\n",
    "                        cur += arr[j]\n",
    "                s[mask.bit_count()].append(cur) \n",
    "            return s\n",
    "\n",
    "        left = get_all(nums[:n])\n",
    "        right = get_all(nums[n:])\n",
    "\n",
    "        for k, v in right.items():\n",
    "            v.sort()\n",
    "        # print(left, right, tot)\n",
    "        ans = inf\n",
    "        half = tot // 2\n",
    "        for le, v in left.items():\n",
    "            need = n - le\n",
    "            cand = right[need]\n",
    "            # if need == 1:\n",
    "            #     print(cand)\n",
    "            for num in v:\n",
    "                idx = bisect.bisect_right(cand, half - num)\n",
    "                # if need == 1:\n",
    "                #     print(num, idx, half - )\n",
    "                if idx < len(cand):\n",
    "                    ans = min(ans, abs(tot - num - cand[idx] - num - cand[idx]))\n",
    "                if idx > 0:\n",
    "                    ans = min(ans, abs(tot - num - cand[idx - 1] - num - cand[idx - 1]))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        m = 1 << n\n",
    "        nums.sort()\n",
    "        total = sum(nums)\n",
    "        half = total // 2\n",
    "        s1 = [0] * m\n",
    "        bitcnt1 = [0] * m\n",
    "        record = [[] for _ in range(n+1)]\n",
    "        record[0].append(0)\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                s = s1[j | bit] = s1[j] + x\n",
    "                c = bitcnt1[j | bit] = bitcnt1[j] + 1\n",
    "                record[c].append(s)\n",
    "        for arr in record:\n",
    "            arr.sort()\n",
    "\n",
    "        ans = abs(s1[-1] * 2 - total)\n",
    "        s2 = [0] * m\n",
    "        bitcnt2 = [0] * m\n",
    "        for i in range(n):\n",
    "            x = nums[i+n]\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                s = s2[j | bit] = s2[j] + x\n",
    "                c = bitcnt2[j | bit] = bitcnt2[j] + 1\n",
    "                idx = bisect_right(record[n-c], half - s)\n",
    "                if idx > 0:\n",
    "                    ss = s + record[n-c][idx-1]\n",
    "                    ans = min(ans, abs(ss * 2 - total))\n",
    "                if idx < len(record[n-c]):\n",
    "                    ss = s + record[n-c][idx-1]\n",
    "                    ans = min(ans, abs(ss * 2 - total))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        m = len(nums)\n",
    "        n = m // 2\n",
    "        tot = sum(nums)\n",
    "\n",
    "        def get_all(arr):\n",
    "            s = defaultdict(list)\n",
    "            for mask in range(1 << n):\n",
    "                cur = 0\n",
    "                for j in range(n):\n",
    "                    if mask & 1 << j:\n",
    "                        cur += arr[j]\n",
    "                s[mask.bit_count()].append(cur) \n",
    "            return s\n",
    "\n",
    "        left = get_all(nums[:n])\n",
    "        right = get_all(nums[n:])\n",
    "\n",
    "        for k, v in right.items():\n",
    "            v.sort()\n",
    "        \n",
    "        # print(left, right, tot)\n",
    "        ans = inf\n",
    "        half = tot // 2\n",
    "        for le, v in left.items():\n",
    "            need = n - le\n",
    "            cand = right[need]\n",
    "            for num in v:\n",
    "                idx = bisect.bisect_left(cand, half - num)\n",
    "                if idx < len(cand):\n",
    "                    ans = min(ans, abs(tot - num - cand[idx] - num - cand[idx]))\n",
    "                if idx > 0:\n",
    "                    ans = min(ans, abs(tot - num - cand[idx - 1] - num - cand[idx - 1]))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)//2\n",
    "        pre = nums[:n]\n",
    "        post = nums[-n:]\n",
    "        total = sum(nums)\n",
    "        group_pre = defaultdict(list)\n",
    "        group_post = defaultdict(list)\n",
    "        for i in range(1<<n):\n",
    "            sum_pre = 0\n",
    "            sum_post = 0\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    sum_pre += pre[j]\n",
    "                    sum_post += post[j]\n",
    "            cnt = bin(i).count('1')\n",
    "            group_pre[cnt].append(sum_pre)\n",
    "            group_post[cnt].append(sum_post)\n",
    "        for k in group_post:\n",
    "            group_post[k].sort()\n",
    "            group_pre[k].sort()\n",
    "\n",
    "        ans = float('inf')\n",
    "        for k in group_pre:\n",
    "            for sum_pre in group_pre[k]:\n",
    "                i = bisect.bisect_left(group_post[n-k], (total - 2*sum_pre)/2)\n",
    "                for j in [i-1, i, i+1]:\n",
    "                    if 0<=j<len(group_post[n-k]):\n",
    "                        ans = min(ans, abs(2*group_post[n-k][j]+2*sum_pre-total))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        N = 1 << n\n",
    "        arr = {1<<i: _ for i, _ in enumerate(nums)}\n",
    "        sums = [[0, 0] for _ in range(N+1)]\n",
    "        \n",
    "        def calc(m):\n",
    "            vals = [set() for _ in range(n+1)]\n",
    "            vals[0].add(0)\n",
    "            for mask in range(1, N):\n",
    "                pre = mask & (mask-1)\n",
    "                low = mask & (-mask)\n",
    "                sums[mask][0] = sums[pre][0] + arr[low<<m]\n",
    "                sums[mask][1] = sums[pre][1] + 1\n",
    "                vals[sums[mask][1]].add(sums[mask][0])\n",
    "            return [sorted(x) for x in vals]\n",
    "        \n",
    "        left, right = calc(0), calc(n)\n",
    "        target = (sum(nums) + 1)//2\n",
    "        ans = float('inf')\n",
    "        for i in range(n+1):\n",
    "            a, b = left[i], right[n-i]\n",
    "            x, y = len(a), len(b)\n",
    "            l, r = 0, y-1\n",
    "            while l < x and r >= 0:\n",
    "                tot = a[l] + b[r]\n",
    "                if tot == target:\n",
    "                    ans = tot\n",
    "                    break\n",
    "                if tot > target:\n",
    "                    ans = min(tot, ans)\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return ans*2 - sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 2\n",
    "        left = defaultdict(set)\n",
    "        right = defaultdict(set)\n",
    "        for mask in range(1 << n):\n",
    "            l1, r1 = 0, 0\n",
    "            l2, r2 = 0, 0\n",
    "            bit = bin(mask).count('1')\n",
    "            for i in range(n):\n",
    "                if (1 << i) & mask:\n",
    "                    l1 += nums[i]\n",
    "                    l2 += nums[i + n]\n",
    "                else:\n",
    "                    r1 += nums[i]\n",
    "                    r2 += nums[i + n]\n",
    "            left[bit].add(l1 - r1)\n",
    "            right[bit].add(l2 - r2)\n",
    "        ans = inf\n",
    "        for l in left:\n",
    "            r = n - l\n",
    "            a = sorted(left[l])\n",
    "            for x in right[r]:\n",
    "                i = bisect.bisect_left(a, -x)\n",
    "                cur = inf\n",
    "                if i < len(a):\n",
    "                    cur = min(cur, abs(a[i] + x))\n",
    "                else:\n",
    "                    cur = min(cur, abs(a[i-1] + x))\n",
    "                ans = min(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def minimumDifference(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        half = n >> 1\n",
    "        left = {}\n",
    "        self.process(arr, 0, half, 0, 0, left)\n",
    "        right = {}\n",
    "        self.process(arr, half, n, 0, 0, right)\n",
    "        all = sum(arr)\n",
    "        half_s = all >> 1\n",
    "        ans = sys.maxsize\n",
    "        for k, values in left.items():\n",
    "            set = right[half - k]\n",
    "            for v in values:\n",
    "                loc = set.bisect_right(half_s - v)  # 注意这里的使用\n",
    "                floor_value = set[loc - 1] if loc != 0 else None\n",
    "                if floor_value is not None:\n",
    "                    s1 = v + floor_value\n",
    "                    s2 = all - s1\n",
    "                    ans = min(ans, abs(s1 - s2))\n",
    "        return ans\n",
    "\n",
    "    def process(self, arr, l, r, pick, ss, map):\n",
    "        if l == r:\n",
    "            if pick not in map.keys():\n",
    "                map[pick] = SortedSet()\n",
    "            map[pick].add(ss)\n",
    "            return\n",
    "        self.process(arr, l + 1, r, pick, ss, map)\n",
    "        self.process(arr, l + 1, r, pick + 1, ss + arr[l], map)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def minimumDifference(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        half = n >> 1\n",
    "        left = {}\n",
    "        self.process(arr, 0, half, 0, 0, left)\n",
    "        right = {}\n",
    "        self.process(arr, half, n, 0, 0, right)\n",
    "        all = sum(arr)\n",
    "        half_s = all >> 1\n",
    "        ans = sys.maxsize\n",
    "        for k, values in left.items():\n",
    "            set = right[half - k]\n",
    "            for v in values:\n",
    "                loc = set.bisect_right(half_s - v)  # 注意这里的使用\n",
    "                floor_value = set[loc - 1] if loc != 0 else None\n",
    "                if floor_value is not None:\n",
    "                    s1 = v + floor_value\n",
    "                    s2 = all - s1\n",
    "                    ans = min(ans, abs(s1 - s2))\n",
    "        return ans\n",
    "\n",
    "    def process(self, arr, l, r, pick, ss, map):\n",
    "        if l == r:\n",
    "            if pick not in map.keys():\n",
    "                map[pick] = SortedSet()\n",
    "            map[pick].add(ss)\n",
    "            return\n",
    "        self.process(arr, l + 1, r, pick, ss, map)\n",
    "        self.process(arr, l + 1, r, pick + 1, ss + arr[l], map)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        from sortedcontainers import SortedList\n",
    "        m = defaultdict(SortedList)\n",
    "\n",
    "        def dfs1(i, c, s):\n",
    "            if i == n // 2:\n",
    "                m[c].add(s)\n",
    "                return\n",
    "            dfs1(i + 1, c + 1, s + nums[i])\n",
    "            dfs1(i + 1, c, s)\n",
    "        \n",
    "        ss = sum(nums) \n",
    "        dfs1(0, 0, 0)\n",
    "        minl = inf\n",
    "        def dfs2(i, c, s):\n",
    "            if i == n:\n",
    "                c2 = n // 2 - c\n",
    "                nonlocal minl\n",
    "                idx = m[c2].bisect_right((ss - 2* s) / 2)\n",
    "                if idx < len(m[c2]): \n",
    "                    s1 = m[c2][idx]\n",
    "                    left = s1 + s\n",
    "                    right = ss - s1 - s\n",
    "                    minl = min(minl, abs(left - right))\n",
    "                if idx - 1 >= 0:\n",
    "                    s1 = m[c2][idx - 1]\n",
    "                    left = s1 + s\n",
    "                    right = ss - s1 - s\n",
    "                    minl = min(minl, abs(left - right))\n",
    "                return\n",
    "            dfs2(i + 1, c + 1, s + nums[i])\n",
    "            dfs2(i + 1, c, s)\n",
    "        \n",
    "        dfs2(n // 2, 0, 0)\n",
    "        return minl"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
